package com.sicheng.lc.周赛.分类.图论.拓扑排序;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/20 22:04
 */
public class 顺丰鄂州枢纽运转中心环线检测 {
    public boolean hasCycle(String graph) {
        String[] g = graph.split(",");
        int[] st = new int[100];
        HashMap<Integer, Set<Integer>> next = new HashMap<>();

        int count = 0;
        for (String s : g) {
            int i = s.indexOf("-");
            int a = Integer.parseInt(s.substring(0, i));
            int b = Integer.parseInt(s.substring(i + 2));
            count = Math.max(count, Math.max(a, b));
            next.computeIfAbsent(a, k -> new HashSet<>()).add(b);
            st[b]++;
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 1; i <= count; i++) {
            if (st[i] == 0) {
                deque.offer(i);
            }
        }

        if (deque.isEmpty())
            return true;

        int t = count;
        count = 0;
        while (!deque.isEmpty()) {
            int x = deque.poll();
            count++;
            Set<Integer> s = next.get(x);
            if (s != null && s.size() > 0) {

                for (int i : s) {
                    st[i]--;
                    if (st[i] == 0)
                        deque.offer(i);
                }
            }
        }

        return count != t;
    }

    public static void main(String[] args) {
        顺丰鄂州枢纽运转中心环线检测 solution = new 顺丰鄂州枢纽运转中心环线检测();
        boolean ok =
                solution.hasCycle("1->2,2->3,3->1");
        System.out.println(ok);
    }
}
